package com.kznnc.data_structure.algorithm;

/**
 * @Description 动态规划算法
 * @Author houchenkai
 * @Created Date: 2021/7/12 18:05
 * @ClassName
 */
public class DynamicPlanningAlgorithm {


    public static void main(String[] args) {
        int[] value = {60, 100, 120};
        int[] weight = {10, 20, 40};
        int w = 50;
        int n = 3;

        // n表示是物品,w表示重量,初始化全是0
        int[][] dp = new int[n + 1][w + 1];
        // 每次加的物品
        for (int i = 1; i <= n; i++) {
            //分割背包
            for (int cw = 1; cw <= w; cw++) {
                //表示这个物品可以放进去
                if (weight[i - 1] <= cw) {
                    dp[i][cw] = Math.max(
                            value[i - 1] + dp[i - 1][cw - weight[i - 1]],
                            dp[i - 1][cw]
                    );
                } else {
                    dp[i][cw] = dp[i - 1][cw];
                }
            }

        }
        System.out.println(dp[n][w]);

    }
}
